The disclosed invention relates in general to computers utilizing virtual addresses and physical addresses and relates more particularly to computers that utilize translation lookaside buffers (TLBs) in the translation of virtual addresses to physical addresses. In a computer environment, virtual addresses are utilized by the software to reference instructions and data whereas physical addresses are the actual physical locations in memory where the instructions and data are stored. The utilization of both types of addresses requires that there be a translation from virtual addresses to physical addresses so that an address referenced in software will result in access of the associated physical address.
In general, the space of virtual addresses will be much larger than the space of physical addresses. The virtual address and physical address spaces are typically divided into equal size blocks of memory called pages so that the translation from virtual address to physical address involves a translation of virtual page numbers to physical page numbers. A page directory (PDIR) provides the translation between virtual addresses and physical addresses. The page directory contains an entry for every physical page number that has been associated with a virtual page number. Therefore, direct use of the page directory to perform the translations is typically too slow. In order to increase the speed of translation, many computers utilize a cache memory referred to as a translation lookaside buffer (TLB) to assist in the translation of virtual addresses to physical addresses.
An advantage of cache memory is that a memory access to it is typically much faster than a memory access to main memory. Typically, this increased access speed requires that the cache memory be small. In many cases, the TLB cannot contain the entire page directory so that procedures need to be implemented to update the TLB. When a virtual page is accessed that is not in the TLB, the page directory is accessed to determine the translation of this virtual page number to a physical page number and this information is entered into the TLB. Access to the page directory can take on the order of fifty times longer than access to the TLB and therefore program execution speed is optimized by keeping the translations being actively utilized in the TLB.
In many systems, the physical memory consists of a backing memory (such as disc memory or tape memory), main memory and cache memory. The backing memory is typically larger than the main memory, thereby enabling larger programs to be implemented than if only main memory were available. Depending on the length of a program and on the competition with other programs for the main memory, part or all of a program is loaded into main memory at a given time. Only part of the program segment in main memory can be loaded from main memory into the cache memory. Memory caches are based on the assumption that, because a particular memory location has been referenced, that location and locations very close to it are very likely to be accessed in the near future. This property is referred to as locality. Therefore, the cache will contain data that was recently referenced and the TLB will contain translations associated with those pages.
In FIG. 1 is illustrated the response to the presentation (step 11) of a virtual address during program execution. If the translation for that virtual address is in the TLB (referred to as a TLB hit), then the associated physical address is derived from the TLB and is utilized to access physical memory (step 12). If the translation for that virtual address is not in the TLB (referred to as a TLB miss), then the translation for that virtual address is sought in the page directory (step 13). If the translation is in the page directory, then this information is inserted into the TLB (step 14) and the virtual address is again presented (step 11). This time we are assured of a TLB hit so that the resulting physical address is used to access physical memory.
If the virtual address is in a page of virtual addresses for which no page of physical addresses is associated, then there will be no entry for this page in the page directory. Such an occurrence is called a page fault. In response to a page fault, the virtual page that is referenced is assigned a physical page (step 15) and this information is inserted into the page directory. If all physical pages had already been associated with other virtual pages, then the page fault handler needs to select which of the physical pages to reassign to the virtual address page currently being referenced. There are many algorithms for such a choice including first-in-first-out and least-recently-used algorithms. Because this entire process is more complicated than those routines typically implemented in microcode, the page fault handler is typically implemented in software. Microcode is typically kept simple so that it can fit into the relatively small and fast memories utilized to store microcode.
After completion of the page fault handler routine, the virtual address is again presented (step 11). The TLB does not yet have the translation so that there will be a TLB miss. Therefore, the translation is looked up in the page directory (step 13), the translation is inserted into the TLB (step 14) and the virtual address is presented for a third time (step 11). This time a TLB hit is assured so that the resulting physical address is used to access physical memory.
The above procedure has the disadvantage that it requires accessing the page directory twice. This is disadvantageous because looking up a translation in the page directory can take on the order of fifty times as long as looking up a translation in the TLB. In accordance with the present invention, a set of software instructions are introduced that enable the software to insert the translation directly into the TLB. This enables the page fault handler to insert the translation not only in the page directory, but also to insert the information into the TLB. Therefore, after completion of the page fault handler routine, instead of being assured that there will be a TLB miss, it is assured that there will be a TLB hit.
In many embodiments of computers using TLBs and cache memories, there is a cache for instructions and a separate cache for data. In addition there are separate TLBs for the instruction cache and the data cache. In such embodiments, there are separate software instructions that enable translations to be inserted directly into the data TLB and into the instruction TLB. Likewise, in some embodiments, it is advantageous for each of these capabilities to be implemented by a pair of instructions. In one particular embodiment, the first of these instructions inserts the translation between the virtual page number and its associated physical page number. The second of these instruction inserts any protection information, flags or other information that is of use for verifying the legality of the access to the page.